﻿namespace LeetCodeProject._0001_1000._001_100._31_40._033;

public class Solution
{
    public int Search(int[] nums, int target)
    {
        if (nums == null || nums.Length == 0)
            return -1;

        var hi = nums.Length - 1;
        var low = 0;

        while (low <= hi)
        {
            var mid = low + (hi - low) / 2;
            var midVal = nums[mid];
            if (midVal == target)
                return mid;

            if (nums[low] <= midVal)
            {
                if (nums[low] <= target && target <= midVal)
                    hi = mid - 1;
                else
                    low = mid + 1;
            }
            else
            {
                if (midVal <= target && target <= nums[hi]) low = mid + 1;
                else
                    hi = mid - 1;
            }
        }

        return -1;
    }
}